1. Field of the Invention
The present invention generally relates to digital signal encoding and for this purpose provides a method and a device for encoding a digital signal.
The object of the encoding is to compress the signal, which makes it possible respectively to transmit the digital signal and to store it in memory while reducing the transmission time, or the transmission rate respectively, by reducing the space in memory that is used.
The invention is in the field of lossy compression of digital signals. The digital signals considered here are of any type, for example fixed images, video, sound, or computer data.
2. Related Art
In what follows, the encoding and decoding of a fixed image will more particularly be considered.
In this context, certain encoding modes use a path established between a set of digital samples. For example, French patent applications No. 01 06933, 01 12064 and 01 13922 concern such encoding modes.
For the encoding to be efficient, that is to say for it to have a good rate-distortion ratio, it is necessary to determine the path in an appropriate manner.
Techniques exist to determine a path between a set of samples. These techniques are known as techniques for solving the traveling salesman problem. A review of these techniques is for example set out in the work of Gerhard Reinelt entitled “The traveling salesman, computational solutions for TSP applications”, Springer-Verlag, 1994.
Generally it is desired that the result of the encoding be as compact as possible. Thus, in the case of encoding using a path established between a set of digital samples, the path is described by the shortest possible path (traveling salesman problem). The shorter the displacement vectors linking each point of the path, the more compact will be the result of their encoding.